Search for: All records

We study monotone cellular automata (also known as ‐bootstrap percolation) in with random initial configurations. Confirming a conjecture of Balister, Bollobás, Przykucki and Smith, who proved the corresponding result in two dimensions, we show that the critical probability is non‐zero for all subcritical models.

For a given graphH, we say that a graphGonnvertices isH‐saturated ifHis not a subgraph ofG, but for any edgethe graphcontains a subgraph isomorphic to H. The set of all valuesmfor which there exists anH‐saturated graph onnvertices andmedges is called the edge spectrum forH‐saturated graphs. In the present article, we study the edge spectrum forH‐saturated graphs whenHis a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number.

We study a new geometric bootstrap percolation model,line percolation, on thed‐dimensional integer grid. In line percolation with infection parameterr, infection spreads from a subsetof initially infected lattice points as follows: if there exists an axis‐parallel lineLwithror more infected lattice points on it, then every lattice point ofonLgets infected, and we repeat this until the infection can no longer spread. The elements of the setAare usually chosen independently, with some densityp, and the main question is to determine, the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determineup to a multiplicative factor ofandup to a multiplicative constant asfor every fixed. We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.